package com.tree.leetcode.array;

import cn.hutool.json.JSONUtil;

import java.util.HashMap;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 560. 和为 K 的子数组
 * <p>
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。



示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

 * </p>
 * @Author tree
 * @Date 1/28/24 3:08 PM
 * @Version 1.0
 */
public class SubarraySum_560 {

    public static void main(String[] args) {
        int[] nums = {1,2,3}; int k = 3;
//
//        int[] nums = {1,1,1}; int k = 2
//
//        int[] nums = {-1,-1,1}; int k= 0;
//        int[] nums = {1,-1,0}; int k= 0;
        System.out.println(subarraySum2(nums,k));
    }

    public static int subarraySum(int[] nums, int k) {

        int sum = 0;
        int count = 0;
        for(int i =0 ; i< nums.length; i++){
            for(int j = i; j < nums.length ; j++){
                sum += nums[j];
                if(sum == k){
                    System.out.println("i = "+ i+"; j ="+j+";sum = "+sum+ ";count="+count);
                    count++;

//                    break;
                }
            }
            sum = 0;

        }


        return count;
    }


    /**
     * 前缀和
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum2(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap< Integer, Integer > mp = new HashMap();
        //初始化前面第一位， 0出现的次数为1次
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
                System.out.println("pre="+pre+",i="+i+"; mp="+JSONUtil.toJsonStr(mp));
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        System.out.println(JSONUtil.toJsonStr(mp));
        return count;
    }

}
